package problems.daily;

/**
 * 878. 第 N 个神奇数字
 * <p>https://leetcode.cn/problems/nth-magical-number/</p>
 *
 * @author habitplus
 * @since 19:46, 2022/11/22
 */
public class DT878 {
    // TME
    public int nthMagicalNumber1(int n, int a, int b) {
        long p1 = 0, p2 = 0, t1, t2;
        long ret = 0;
        final int MOD = (int) (1e9 + 7);

        while (n-- > 0) {
            t1 = (p1 + a) % MOD;
            t2 = (p2 + b) % MOD;

            if (t1 > t2) {
                p2 = t2;
            } else if (t1 < t2) {
                p1 = t1;
            } else {
                p1 = t1;
                p2 = t2;
            }

            ret = Math.min(t1, t2);
        }

        return (int) ret;
    }


    static final int MOD = 1000000007;

    public int nthMagicalNumber(int n, int a, int b) {
        long l = Math.min(a, b);
        long r = (long) n * Math.min(a, b);
        int c = lcm(a, b);
        while (l <= r) {
            long mid = (l + r) / 2;
            long cnt = mid / a + mid / b - mid / c;
            if (cnt >= n) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return (int) ((r + 1) % MOD);
    }

    public int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

    public int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }



}
